Designing delivery districts for the vehicle routing problem with stochastic demands

This paper considers the problem of designing districts for vehicle routing problems with stochastic demands. In particular, demands are assumed to be uncertain at the time when the districts are made, and these are revealed only after the districting decisions are determined. Tabu search and multistart heuristics for this stochastic districting problem are developed and compared. Computational results show that tabu search is superior over multistart.     

Extension of the 2-p-opt and 1-shift algorithms to the heterogeneous probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a well known problem that is quite challenging to solve. It involves finding the tour with the lowest expected cost for customers that will require a visit with a given probability. There are several proposed algorithms for the homogeneous version of the problem, where all customers have identical probability of being realized. From the literature, the most successful approaches involve local search procedures, with the most famous being the 2-p-opt and 1-shift procedures proposed by Bertsimas [D.J. Bertsimas, L. Howell, Further results on the probabilistic traveling salesman problem, European Journal of Operational Research 65 (1) (1993) 68–95]. Recently, however, evidence has emerged that indicates the equations offered for these procedures are not correct, and even when corrected, the translation to the heterogeneous version of the problem is not simple. In this paper we extend the analysis and correction to the heterogeneous case. We derive new expressions for computing the cost of 2-p-opt and 1-shift local search moves, and we show that the neighborhood of a solution may be explored in O(n²) time, the same as for the homogeneous case, instead of O(n³) as first reported in the literature.     

Optimizing the periodic pick-up of raw materials for a manufacturer of auto parts

We describe a solution procedure for a special case of the periodic vehicle routing problem (PVRP). Operation managers at an auto parts manufacturer in the north of Spain described the optimization problem to the authors. The manufacturer must pick up parts (raw material) from geographically dispersed locations. The parts are picked up periodically at scheduled times. The problem consists of assigning a pickup schedule to each of its supplier’s locations and also establishing daily routes in order to minimize total transportation costs. The time horizon under consideration may be as long as 90 days. The resulting PVRP is such that the critical decision is the assignment of locations to schedules, because once this is done, the daily routing of vehicles is relatively straightforward. Through extensive computational experiments, we show that the metaheuristic procedure described in this paper is capable of finding high-quality solutions within a reasonable amount of computer time. Our main contribution is the development of a procedure that is more effective at handling PVRP instances with long planning horizons when compared to those proposed in the literature.     

Planning and approximation models for delivery route based services with price-sensitive demands

Classical vehicle routing problems typically do not consider the impact of delivery price on the demand for delivery services. Existing models seek the minimum sum of tour lengths in order to serve the demands of a given set of customers. This paper proposes approximation models to estimate the impacts of price on delivery services when demand for delivery service is price dependent. Such models can serve as useful tools in the planning phase for delivery service providers and can assist in understanding the economics of delivery services. These models seek to maximize profit from delivery service, where price determines demand for deliveries as well as the total revenue generated by satisfying demand. We consider a variant of the model in which each customer’s delivery volume is price sensitive, as well as the case in which customer delivery volumes are fixed, but the total number of customers who select the delivery service provider is price sensitive. A third model variant allows the delivery service provider to select a subset of delivery requests at the offered price in order to maximize profit.     

Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia

In this work we present a multiobjective location routing problem and solve it with a multiobjective metaheuristic procedure. In this type of problem, we have to locate some plants within a set of possible locations to meet the demands of a number of clients with multiple objectives. This type of model is used to solve a problem with real data in the region of Andalusia (Spain). Thus, we study the location of two incineration plants for the disposal of solid animal waste from some preestablished locations in Andalusia, and design the routes to serve the different slaughterhouses in this region. This must be done while taking into account certain economic objectives (start-up, maintenance, and transport costs) and social objectives (social rejection by towns on the truck routes, maximum risk as an equity criterion, and the negative implications for towns close to the plant).     

A flexible adaptive memory-based algorithm for real-life transportation operations: Two case studies from dairy and construction sector

Effective routing of vehicles remains a focal goal of all modern enterprises, thriving for excellence in project management with minimal investment and operational costs. This paper proposes a metaheuristic methodology for solving a practical variant of the well-known Vehicle Routing Problem, called Heterogeneous Fixed Fleet VRP (HFFVRP). Using a two-phase construction heuristic, called GEneralized ROute Construction Algorithm (GEROCA), the proposed metaheuristic approach enhances its flexibility to easily adopt various operational constraints. Via this approach, two real-life distribution problems faced by a dairy and a construction company were tackled and formulated as HFFVRP. Computational results on the aforementioned case studies show that the proposed metaheuristic approach (a) consistently outperforms previous published metaheuristic approaches we have developed to solve the HFFVRP, and (b) substantially improves upon the current practice of the company. The key result that impressed both companies’ management was the improvement over the bi-objective character of their problems: the minimization of the total distribution cost as well as the minimization of the number of the given heterogeneous number of vehicles used.     

An application of Special Ordered Sets to a periodic milk collection problem

We present an OR-based approach to support a milk collection problem in a special branch of dairy industry. The annual growth of the sector and the continuous imbalance between milk supply and demand, has urged the sector to look for a different approach to their daily milk collection problem. Specific details of the problem environment (i.e., the continuous production on supply level and the delivery conditions on demand level) gave rise to choose for a short- to medium-term planning approach. The proposed decision support system has to be considered as an efficient tool for generating stable milk collection plans which in turn also serves as an effective starting point for the vehicle routing problem. From a computational point of view it turned out that the application of Special Ordered Sets type 1 (SOS1) was very useful. Although it appears from literature that the computational advantage of SOS1 is restricted to supplementary model conditions, this study shows that these conditions are not necessarily needed.     

求解无线传感器网络路由问题的蚁群最优化算法及其收敛性

首先将无线传感器网络的路由问题转化成求解最小Steiner树问题,然后给出了求解无线传感器网络路由的蚁群优化算法,并对算法的收敛性进行了证明．最后对找到最优解后信息素值的变化进行了分析．即在限制信息素取值的条件下,当迭代次数充分大时,该算法能以任意接近于1的概率找到最优解,并且当最优解找到后,最优树边上的信息素单调增加,而最优解以外边上的信息素在有限步达到最小值．     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。     

The Sample Average Approximation Method Applied to Stochastic Routing Problems: A Computational Study

The sample average approximation (SAA) method is an approach for solving stochastic optimization problems by using Monte Carlo simulation. In this technique the expected objective function of the stochastic problem is approximated by a sample average estimate derived from a random sample. The resulting sample average approximating problem is then solved by deterministic optimization techniques. The process is repeated with different samples to obtain candidate solutions along with statistical estimates of their optimality gaps.We present a detailed computational study of the application of the SAA method to solve three classes of stochastic routing problems. These stochastic problems involve an extremely large number of scenarios and first-stage integer variables. For each of the three problem classes, we use decomposition and branch-and-cut to solve the approximating problem within the SAA scheme. Our computational results indicate that the proposed method is successful in solving problems with up to 2¹⁶⁹⁴ scenarios to within an estimated 1.0% of optimality. Furthermore, a surprising observation is that the number of optimality cuts required to solve the approximating problem to optimality does not significantly increase with the size of the sample. Therefore, the observed computation times needed to find optimal solutions to the approximating problems grow only linearly with the sample size. As a result, we are able to find provably near-optimal solutions to these difficult stochastic programs using only a moderate amount of computation time.